home *** CD-ROM | disk | FTP | other *** search
/ System Booster / System Booster.iso / Archives / ForCLI / AGrep204.lha / agrep.chronicle < prev    next >
Text File  |  1992-03-16  |  3KB  |  65 lines
  1. This chronicle briefly describes the progress of agrep.
  2.  
  3. Feb/91: The approximate pattern matching algorithm called 'bitap'
  4.     (bit-parallel approximate pattern matching) is designed.
  5.     The algorithm is a generalization of Baeza-Yates' "shift-or"
  6.     algorithm for exact matching.
  7.  
  8. Mar/91: Many extensions of the algorithm 'bitap' are found, especially
  9.     for approximate regular expression pattern matching.  Preliminary
  10.     implementation of the algorithm showed a strong promise for 
  11.     a general-purpose fast approximate pattern-matching tool.
  12.  
  13. Apr/91: Approximate regular expression pattern matching was implemented.
  14.     The result is even better than expected. 
  15.     The design of the software tool is pinned down.
  16.     (For example, record oriented, multi-pattern, AND/OR logic queries.)
  17.     A partition technique for approximate pattern matching is used.
  18.     
  19. May/91: The prototype of "agrep" is completed.
  20.     A lot of debugging/optimization in this month.
  21.  
  22. Jun/91: The first version of agrep is released.
  23.     agrep 1.0 was announced and made available by anonymous ftp 
  24.     from cs.arizona.edu.
  25.  
  26. Jul/91: A sub-linear expected-time algorithm, called "amonkey" for 
  27.     approximate pattern matching (for simple pattern) is designed.
  28.     The algorithm has the same time complexity as that of
  29.     Chang&Lawler but is much much faster in practice.
  30.     The algorithm is based on a variation of Boyer-Moore technique,
  31.     which we call "block-shifting." 
  32.     A sub-linear expected-time algorithm, called "mgrep" for 
  33.     matching a set of patterns is designed based on the "block-shifting" 
  34.     technique with a hashing technique.
  35.  
  36. Aug/91: "amonkey" is implemented and incorporated into agrep.
  37.     It is very fast for long patterns like DNA patterns.
  38.     (But roughly the same for matching English words as the bitap
  39.     algorithm using the partition technique.)
  40.     Prototype of "mgrep" is implemented.
  41.  
  42. Sep/91: "mgrep" is incorporated into agrep to support the -f option.
  43.     An algorithm for approximate pattern matching that combines the 
  44.     'partition' technique with the sub-linear expected-time algorithm 
  45.     for multi-patterns is designed.
  46.     Implementation shows it to be the fastest for ASCII text (and pattern).
  47.     Boyer-moore technique for exact matching is incorporated.
  48.  
  49. Nov/91: The final paper of "agrep" that is to appear in USENIX
  50.     conference (Jan 1992)  is finished.
  51.  
  52. Jan/92: Some new options are added, such as find best matches (-B), 
  53.     and file outputs (-G).
  54.     The man pages are revised.
  55.     agrep version 2.0 is released.
  56.     Fixed the following bugs and change the version to be 2.01.
  57.     1. -G option doesn't work correctly.
  58.     2. multiple definition of some global variables.
  59.     3. -# with -w forced the first character of the pattern to be matched
  60.  
  61. Mar/92: Fixed the following bugs and change the version to be 2.02.
  62.     1. agrep sometimes misses some matches for pipeline input.
  63.     2. the word delimiter was not defined consistantly.
  64.  
  65.